\section{Introdução}

\subsection{Criptografia e criptografia moderna}
\frame{
  \frametitle{Definição de criptografia}
  \begin{itemize}
      \item Definição dada pelo dicionário de Oxford: \textit{``A arte de
       escrever e resolver códigos.'' } \\
     \vfill
      \item Foca exclusivamente no problema do sigilo na comunicação.\\
     \vfill 
      \item Referência a criptografia como uma forma de arte.\\ 
      \vfill
     \end{itemize}
}

\frame{
  \frametitle{Criptografia Clássica}
  \begin{itemize}
       \item Até o final do século passado a criptografia era uma
         arte.\\
         \vfill
        \item A construção de bons códigos, ou a quebra dos existentes
          dependia da criatividade e habilidade pessoal.\\
       \vfill 
        \item Existia pouca teoria na qual se podia confiar e nem
           mesmo uma boa definição do que constituía um bom código.\\ 
    \end{itemize}
}

\frame{
  \frametitle{Criptografia Moderna}
  \begin{itemize}
       \item Uma definição de criptografia moderna: \textit{``O
            estudo científico de técnicas para proteger informações
            digitais, transações e computações distribuídas.''}  
      \vfill 
       \item No final do século passado surge uma rica teoria,
         possibilitando um estudo rigoroso da criptografia como
         ciência.
         \vfill
        \item O campo da criptografia engloba muito mais do que
          sigilo na comunicação.
          \vfill
        \item Trata problemas como autenticação de mensagens,
          assinaturas digitais, protocolo para troca de chaves,
          protocolos de autenticação, dinheiro digital, leilões e eleições eletrônicas.
       \end{itemize}
}

\frame{
  \frametitle{Mudanças no uso da criptografia}
  \begin{itemize}
    \item A criptografia antes da década de 80 era utilizada na
      maioria das vezes por militares ou agências de inteligência.\\
      \vfill
     \item Atualmente a criptografia está em todos os lugares!\\ 
       \vfill
     \item Os mecanismos de segurança que se baseiam em criptografia
       são parte integrante da maioria dos sistemas de computação.\\
       \vfill
      \item A criptografia saiu de uma forma de arte com o intuito de
        tratar sigilo nas comunicações de militares para uma ciência
        a qual provê sistemas seguros para pessoas comuns em todo o
        mundo.\\

  \end{itemize}
}

\subsection{Chave simétrica}
\frame{
  \frametitle{Chave privada ou chave simétrica}
  \begin{itemize}
    \item Duas partes compartilham alguma informação secreta chamada
      chave, utilizam esta para se comunicar de forma sigilosa um
      com o outro.
      \vfill
    \item O emissor utiliza a chave para cifrar (embaralhar) a
      mensagem. 
      \vfill
    \item O receptor utiliza a chave para decifrar (desembaralhar) a mensagem. 
      \vfill
    \item A mensagem é chamada texto em claro. 
      \vfill
    \item A mensagem embaralhada é chamada de texto cifrado. 
      \vfill
 \end{itemize}
}

\frame{
  \frametitle{Chave privada ou chave simétrica}
  \begin{itemize}
    \item A chave privada serve para distinguir as partes da
      comunicação de possíveis intrusos escutando o canal de comunicação. \\
      \vfill
    \item Como a mesma chave serve para cifrar e decifrar, este
      protocolo é conhecido como protocolo de chave simétrica.
  \end{itemize}
  \begin{figure}[!h]
	\centering
	\includegraphics[scale=0.3]{imagens/esquemaChaveSimetrica.png}
	\caption{Esquema simples de chave privada~\cite{katz}.}\label{esquemaChaveSimetrica}
   \end{figure}
}

\frame{
  \frametitle{Premissa de confiança no esquema de chave privada}
  \begin{itemize}
    \item A existência de um canal seguro, o qual as partes podem
      utilizar para compartilhar a chave.\\
      \vfill
     \item Sigilo da chave privada.
     \vfill
    \item Na área militar isto não é um problema, pois as partes da
      comunicação podem se encontrar fisicamente em um local seguro.\\
      \vfill
    \item Porém no uso moderno da criptografia as partes são incapazes
      de se encontrar fisicamente. Nesta situação o esquema de chave
      simétrica não é adequado. Este problema estimulou o
      desenvolvimento do esquema de chave pública.\\
      \vfill

  \end{itemize}
}

\subsubsection{A sintaxe da cifragem}
\frame{
  \frametitle{O esquema de chave simétrica é composto por 3 algoritmos}
  \begin{itemize}
    \item O algoritmo de geração da chave $Gen$ é um algoritmo
      probabilístico que fornece uma chave $k$ escolhida de acordo com
      alguma distribuição determinada pelo esquema.\\
      \vfill
     \item O algoritmo de cifragem $Enc$ recebe uma chave $k$ e uma
       mensagem em texto em claro $m$ e fornece o texto cifrado $c$.
       Denota-se $Enc_{k}(m)$ a cifragem do texto em claro $m$ utilizando a
       chave $k$.\\
      \vfill
    \item O algoritmo de decifragem $Dec$ recebe uma chave $k$ e um
      texto cifrado $c$ e fornece a mensagem em texto em claro
      $m$. Denota-se $Dec_{k}(c)$ a decifragem do texto cifrado $c$
      utilizando a chave $k$.\\
      \vfill
  \end{itemize}
}

\frame{
  \frametitle{Chave simétrica}
  \begin{itemize}
    \item O conjunto de todas as chaves possíveis é chamado espaço de
      chaves denotado por $\mathcal{K}$.\\
      \vfill
     \item Na maioria das vezes, $Gen$ simplesmente escolhe uma chave
       uniformemente (com a mesma probabilidade) em um espaço de chaves. \\
       \vfill
     \item O conjunto de todas as mensagens suportadas pelo algoritmo
       de cifragem é denotado por $\mathcal{M}$ e é chamado por espaço de
       mensagens.
\end{itemize}
}

\frame{
  \frametitle{Chave simétrica}
  \begin{itemize}
    \item Como todo texto cifrado é obtido a partir de algum texto
        pleno e uma chave, os conjuntos $\mathcal{K}$ e $\mathcal{M}$ definem o
        conjunto de todos possíveis textos cifrados denotado por $C$.
        \vfill
        \item O esquema de chave simétrica é totalmente definido pelos
          3 algoritmos $(Gen,Enc,Dec)$ e pelo espaço de mensagens
          $\mathcal{M}$. 
         \vfill
         \item O requisito básico de corretude de qualquer esquema de
           cifragem é que para toda chave $k$ obtida através do
           algoritmo $Gen$ e para todo texto em claro $m \in \mathcal{M}$, a
           seguinte sentença valha $Dec_{k}(Enc_{k}(m))=m$ .
\end{itemize}
}

\frame{
  \frametitle{Passos do protocolo de chave simétrica}
  \begin{itemize}
           \item Através do algoritmo $Gen$ obtém-se a chave privada,
             esta é compartilhada entre as partes.\\
             \vfill
            \item O emissor cifra a mensagem $m$, $c := Enc_{k}(m)$, e
              envia o texto cifrado $c$ através do canal público.\\
              \vfill
             \item O receptor decifra o texto cifrado, $m :=
               Dec_{k}(c)$, recuperando a mensagem original.\\
    \end{itemize}
}
\subsubsection{Princípio de Kerckhoﬀs} 
\frame{
  \frametitle{Princípio de Kerckhoffs}
  \begin{itemize}
           \item O método de cifragem não deve requerer sigilo,
             podendo cair na mão do inimigo sem maiores inconvenientes.\\
             \vfill
             \item O princípio requer que a segurança do protocolo
               dependa exclusivamente do segredo da chave.\\
             \vfill
             \item É muito mais simples manter em sigilo apenas a
               chave do que todo o mecanismo de cifragem e decifragem.\\
              \vfill
             \item No caso de vazamento de informação sigilosa é muito mais fácil
               trocar apenas uma chave do que trocar todo o mecanismo.\\
   \end{itemize}
}

\frame{
  \frametitle{Princípio de Kerckhoffs}
  \begin{itemize}
             \item O princípio possibilita o reuso de um mesmo
                algoritmo, só modificando a chave entre o seu uso.
              \vfill
              \item Atualmente o princípio é entendido não somente
                como ``a segurança não deve estar baseada no segredo do
                algoritmo'' mas também como ``os algoritmos devem ser públicos''.
              \vfill
              \item O princípio é o oposto da noção de ``segurança por
               ocultamento'', o qual acredita que existe um acréscimo
                na segurança se o algoritmo criptográfico for mantido
                em sigilo.
              \vfill
    \end{itemize}
}

\frame{
  \frametitle{Vantagens do projeto de uma criptografia aberta}
  \begin{itemize}
            \item Existe uma confiança muito maior na segurança de
              esquemas estudados extensivamente e nenhuma fraqueza
              tenha sido encontrada.\\
             \vfill
             \item É melhor que falhas de segurança sejam reveladas
               por especialistas éticos do que sejam conhecidas
               apenas por partes maliciosas.
              \vfill
             \item Se a segurança do sistema se baseia no segredo do
               algoritmo, então uma engenharia reversa no código constitui uma
               séria ameaça a segurança. Isto é um contraste a chave
               privada a qual não faz parte do código, assim não é
               vulnerável a engenharia reversa.\\
               \vfill
               \item O projeto público possibilita o estabelecimento
                 de padrões.\\
                \vfill
   \end{itemize}
}

\subsubsection{Cenários de ataque}
\frame{
  \frametitle{Cenários de ataque}
  \begin{itemize}
            \item Ataque somente ao texto cifrado: o adversário
              observa o texto cifrado e tenta determinar a mensagem
              original.\\
                \vfill
            \item Ataque de texto em claro conhecido: o adversário
              conhece um ou mais pares de texto claro/texto cifrado
              encriptados com a mesma chave. Tenta descobrir a mensagem
              original de um outro texto cifrado.\\
                \vfill
            \item Ataque de texto em claro escolhido: O adversário
              consegue obter a cifra de um texto em claro a sua
              escolha. Tenta descobrir a mensagem original de um outro
              texto cifrado.\\
                \vfill
            \item Ataque de texto cifrado escolhido: O adversário
              consegue obter as mensagens originais de textos cifrados
              escolhidos por ele. Tenta descobrir a mensagem original
              de um outro texto cifrado, o qual não pode decifrar diretamente.\\
                \vfill
   \end{itemize}
}

 
\subsection{Cifras históricas e suas criptoanálises}

\subsubsection{Cifra de César}
\frame{
  \frametitle{Cifra de César}
  \begin{itemize}
            \item César rotacionava as letras do alfabeto em três
              posições. Por exemplo, a mensagem em texto em claro ``begin
              the attack now'' cifrada, retirando os espaços, fica
              ``EHJLQWKHDWWDFNQRZ''. Uma variante da cifra de César é
              o ROT-13 (desloca 13 posições invés de 3) é muito comum em
              fóruns.\\
                \vfill
  \end{itemize}
  \begin{figure}[!h]
	\centering
	\includegraphics[scale=0.3]{imagens/caesar.png}
	\caption{Rotação das letras na cifra de César.}\label{caesar}
   \end{figure}
}

\subsubsection{A cifra de deslocamento e o princípio de espaço de
  chaves suficiente}

\frame{
  \frametitle{Cifra de deslocamento}
  \begin{itemize}
            \item A cifra de César sofre com o fato da cifragem ser
              feita sempre do mesmo jeito, não existindo uma chave secreta.\\
               \vfill
             \item A cifra de deslocamento é feita da mesma maneira do
               que a cifra de César porém introduz uma chave secreta.\\
               \vfill
             \item A chave secreta é o deslocamento, o qual será
               utilizado na cifragem ou decifragem.\\
               \vfill
             \item O alfabeto pode ser visto como números no intervalo
               $\{0,..,25\}$.\\
 \end{itemize}
}

\frame{
  \frametitle{Cifra de deslocamento}
  \begin{itemize}
            \item O algoritmo $Gen$ fornece a chave secreta
               escolhendo um número aleatoriamente no intervalo $\{0,..,25\}$.\\
               \vfill
             \item O algoritmo $Enc$ de um caracter em texto claro
               $m_{i}$ com uma chave $k$ é dado por $[(m_{i}+k) mod 26]$.\\
               \vfill
             \item O algoritmo $Dec$ de um caracter em texto cifrado
               $c_{i}$ com uma chave $k$ é dado por $[(c_{i}-k) mod 26]$.\\
               \vfill
            \item O espaço de mensagens $\mathcal{M}$ é definido como
              qualquer sequência finita de inteiros pertencentes ao
              intervalo $\{0,..,25\}$.\\
 \end{itemize}
}

\frame{
  \frametitle{Princípio de espaço de chaves suficiente}
  \begin{itemize}
            \item É possível decifrar a seguinte mensagem sem a chave
              secreta, sabendo que foi utilizada uma cifra de deslocamento?\\
               \vfill
             \item OVDTHUFWVZZPISLRLFZHYLAOLYL.\\
               \vfill
             \item Só existem 26 chaves possíveis.\\
               \vfill   
             \item Ataque de força bruta ou busca exaustiva.\\
               \vfill   
              \item Deslocando 19 letras temos a seguinte mensagem:\\
                HOW MANY POSSIBLE KEYS ARE THERE.\\
               \vfill   
  \end{itemize}
}

\frame{
  \frametitle{Princípio de espaço de chaves suficiente}
  \begin{itemize}
            \item Qualquer esquema de criptografia seguro deve possuir
              um espaço de chaves grande o suficiente para não ser
              vulnerável a uma busca exaustiva.\\
               \vfill
            \item Atualmente um ataque força bruta ganhou novas
              proporções com o aumento do poder computacional utilizando
              computação em grid (botnets). Portanto o número de
              possíveis chaves deve ser muito grande, pelo menos
              $2^{60}$ ou $2^{70}$.\\
               \vfill
 \end{itemize}
}

\subsubsection{Cifra de substituição monoalfabética}

\frame{
  \frametitle{Cifra de substituição monoalfabética}
  \begin{itemize}
            \item Este esquema mapeia cada caracter da mensagem
              original para um caracter diferente no texto cifrado de
              maneira arbitrária, apenas respeitando o fato que esse
              mapeamento deve ser feito um para um com o intuito de
              possibilitar a decifragem. 
          \vfill
           \item A chave secreta é a permutação do alfabeto.      
             \vfill
             \item O espaço de chaves consiste em todas as permutações
               do alfabeto, ou seja, $26! = 26 . 25 ... 2 . 1$,
               aproximadamente $2^{88}$. Impossibilitando um ataque
               por força bruta.
             \vfill
             \item A mensagem ``tellhimaboutme'' ficaria cifrado como
               ``GDOOKVCXEFLGCD'' utilizando a permutação da figura~\ref{monoalfabetica}.
  \end{itemize}
  \begin{figure}[!h]
	\centering
	\includegraphics[scale=0.4]{imagens/monoalfabetica.png}
	\caption{Exemplo de permutação do alfabeto~\cite{katz}.}\label{monoalfabetica}
   \end{figure}
}

\frame{
  \frametitle{Ataque a cifra de substituição}
  \begin{itemize}
            \item Considerando que o adversário conheça a língua da
              mensagem original, este pode utilizar propriedades
              estatísticas da língua para quebrar a cifra de substituição.
            \vfill
            \item O ataque se basei em duas propriedades:
           \vfill
  \end{itemize}
  \begin{enumerate}
            \item O mapeamento é fixo então se a letra ``a'' 
é mapeada para a letra ``g'', portanto toda ocorrência da letra ``a''
resultará na ocorrência da letra ``g'' na cifra.
            \vfill 
          \item A frequência média de ocorrência de
            uma letra em uma língua é conhecida. Assim
            quanto maior o texto, mais a frequência de ocorrência da
            letra no texto se aproxima da média.        
 \end{enumerate}
}
\frame{
  \frametitle{Ataque a cifra de substituição}
  \begin{itemize}
            \item O ataque funciona contabilizando a frequência de
              cada letra no texto cifrado, após isso realiza-se uma
              comparação com a frequência de ocorrência média de cada
              letra na língua. 
         \vfill
            \item Tenta-se substituir cada letra do
              texto cifrado por uma letra que tenha frequência de
              ocorrência parecida na língua. 
         \vfill

  \end{itemize}
}

\frame{
  \frametitle{Ataque a cifra de substituição}
  \begin{figure}[!h]
	\centering
	\includegraphics[scale=0.1]{imagens/freqLetras.png}
	\caption{Distribuição de probabilidade das letras na língua inglesa.}\label{freqLetras}
   \end{figure}
}

\subsubsection{Uma melhora no ataque sobre a cifra de deslocamento}

\frame{
  \frametitle{Uma melhora no ataque sobre a cifra de deslocamento}
  \begin{itemize}
         \item Não é trivial para o computador verificar se uma
              mensagem faz sentido em uma determinada língua.
         \vfill
         \item Seja $p_{i}$, para $0 \leq i \leq 25$, denota a
           probabilidade de ocorrência da $i$-ésima letra no alfabeto inglês. Um
           simples cálculo com os valores conhecidos para $p_{i}$, nos
           fornece:\\   \begin{center} $\sum\limits_{i=0}^{25} p_{i}^2
             \simeq 0.065$. \end{center}
          \vfill
          \item Portanto, pode-se automatizar um procedimento que testa
            todos os deslocamentos possíveis e calcula o valor do
            somatório do quadrado das probabilidades. O deslocamento que
            ter seu somatório mais próximo de $0.065$ será a chave. 
           \vfill
  \end{itemize}
}

\subsubsection{Cifra de Vigenère}

\frame{
  \frametitle{Cifra de Vigenère}
  \begin{itemize}
         \item Utiliza-se uma palavra como chave, cada letra dessa
           palavra determinará o deslocamento para cifrar ou
           decifrar. Caso a mensagem seja maior do que a chave esta é
           repetida até que fique do tamanho da mensagem como podemos
           ver na tabela~\ref{exemploVigenere}.\\
         \vfill
         \item Pelo fato uma letra da mensagem poder sofrer
           deslocamentos diferentes dependendo da letra da chave, a
           frequência com que as letras ocorrem na cifra não
           corresponde mais a frequência com que ocorrem na língua
           utilizada na mensagem.\\           
\end{itemize}
\begin{table}[!h]
\caption{Exemplo do uso do Vigenère~\cite{katz}}
\begin{center}
\begin{tabular}{llllllllllllllll}
Texto em claro &t&e&l&l&h&i&m&a&b&o&u&t&m&e\\
Chave &c&a&f&e&c&a&f&e&c&a&f&e&c&a\\
Texto cifrado &W&F&R&Q&K&J&S&F&E&P&A&Y&P&F\\ 
\end{tabular}
\end{center}
\label{exemploVigenere}
\end{table}
}

\subsubsection{Quebrando a cifra de Vigenère}

\frame{
  \frametitle{Quebrando a cifra de Vigenère}
  \begin{itemize}
         \item Caso seja conhecido o tamanho da chave pode-se dividir
           a cifra em várias colunas, desta forma os caracteres de uma
           coluna foram cifrados com o mesmo deslocamento. Desta forma
           pode-se utilizar o mesmo mecanismo da quebra da cifra de
           deslocamento em cada coluna, obtendo cada letra da chave utilizada.\\
         \vfill
         \item Para descobrir o tamanho da chave pode-se utilizar o
           método de Kasiski ou o método do índice de coincidência.\\
          \vfill 
       \item Exemplo de quebra da cifra:
 \end{itemize}
\begin{center} 
\url{http://www.simonsingh.net/The_Black_Chamber/cracking_example.html}
\end{center}         
}

\frame{
  \frametitle{Método de Kasiski}
  \begin{itemize}
         \item Kasiski observou que palavras muito frequentes na língua
           tendem a ser cifradas com a mesma parte da chave durante o texto.\\
        \vfill
        \item Portanto a distância entre padrões iguais tem uma grande
          chance de ser um múltiplo do tamanho da chave.\\
         \vfill
        \item Assim o tamanho da chave será o maior divisor comum entre as distâncias de
          padrões iguais.\\
         \vfill
 \end{itemize}
}

\frame{
  \frametitle{Método do índice de coincidência}
  \begin{itemize}
         \item Este método utiliza-se do somatório visto
           anteriormente, aonde $p_{i}$ é a probabilidade da
           ocorrência da i-ésima letra do alfabeto:
           \begin{center} $\sum\limits_{i=0}^{25} p_{i}^2
             \simeq 0.065$. \end{center}
        \vfill
        \item Ao dividir em colunas a cifra pode-se calcular este
          somatório, assim quanto mais próximo de $0.065$ mais certeza
          que foi utilizado aquele tamanho de chave.
        \vfill
        \item Pode-se iterar com variados tamanhos de chave o que
          chegar mais próximo será o certo.
       \vfill

 \end{itemize}
}



\subsubsection{Conclusões}

\frame{
  \frametitle{Conclusões}
  \begin{itemize}
         \item O princípio do espaço de chaves suficiente: Assumindo
           que mensagens longas serão cifradas, o esquema de
           criptografia deve possuir um espaço de chaves que não possa
           ser explorado por uma busca exaustiva. Um espaço de chaves
           grande é condição necessária, mas não suficiente (cifra
           monoalfabética possui um espaço de chaves grande porém pode
           ser quebrada).
         \vfill
         \item Projetar cifras seguras é uma tarefa difícil: A cifra
           de vigenère permaneceu sem um ataque conhecido durante
           vários anos, parcialmente pela complexidade presumida na
           quebra. Todavia, a complexidade não implica segurança. No geral, é
           difícil projetar um esquema de criptografia seguro,
           portanto isto deve ser deixado para especialistas.
          \vfill
 \end{itemize}
}
